package lee.study.TestSort;

import java.util.Stack;

public class quickSort {
    //快速排序
    //时间复杂度：O(n*log2n)  最坏O（n^2） 8 7 6 5 4 3 2 1/1 2 3 4 5 6 7 8
    //快排每次划分序列的时候，如果可以均匀的划分，效率最好。
    //空间复杂度：O(log2n)   最坏O(n)
    //稳定性：不稳定
    public static int partition(int[] array, int low, int high) {//用于交换的函数
        int tmp = array[low];
        while (low < high) {
            while (low < high && array[high] >= tmp) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;
    }

    public static void insertSort(int[] array, int start, int end) {//直接插入法
        int tmp = 0;
        for (int i = start + 1; i <= end; i++) {
            tmp = array[i];
            int j;
            for (j = i - 1; j >= start; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }


    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void three_num_mid(int[] array, int left, int right) {//三数取中法
        //array[mid] <= array[left]  <= array[right]
        int mid = (left + right) / 2;
        if (array[left] > array[right]) {
            swap(array, left, right);
        }
        if (array[mid] > array[right]) {
            swap(array, mid, right);
        }
        if (array[mid] > array[left]) {
            swap(array, mid, left);
        }
    }

    public static void quick(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        //优化方式一：当待排序序列的数据个数小于等于某个值(这里取100)的时候，采用快速排序。
        if (right - left + 1 <= 100) {
            insertSort(array, left, right);
            return;
        }
        //优化方式二：三数取中法
        three_num_mid(array, left, right);

        int par = partition(array, left, right);

        quick(array, left, par - 1);
        quick(array, par + 1, right);
    }

    public static void quickSort1(int[] array) {
        quick(array, 0, array.length - 1);
    }


    //非递归实现快速排序
    public static void quickSort(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;

        //第一步
        int par = partition(array, left, right);
        if (par > left + 1) {//确保左边有两个数据及以上
            stack.push(left);
            stack.push(par - 1);
        }
        if (par < right - 1) {//确保右边有两个数据及以上
            stack.push(par + 1);
            stack.push(right);
        }

        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            par = partition(array, left, right);
            if (par > left + 1) {
                stack.push(left);
                stack.push(par - 1);
            }
            if (par < right - 1) {
                stack.push(par + 1);
                stack.push(right);
            }
        }

    }
}
